Evaluating dynamic Gröbner Basis algorithms
Gabriel Mattos Langeloh
10/10/2019
Introduction
The goal of this document is to do some exploratory analysis on dynamic Gröbner Basis algorithms. Gröbner bases (GB) are a fundamental tool in computer algebra to solve multivariate polynomial (non-linear) systems, among other applications. Traditional static Gröbner Basis algorithms receive an ordering (a vector) as part of the input. The performance of the algorithm, as well as the size of the output itself strongly depends on this input ordering. Dynamic Gröbner Basis algorithms were proposed to avoid having to choose an ordering a priori, computing one during the execution of the algorithm itself, hoping that this would lead to at least some of the following:
- shorter computation times
- fewer polynomials in the output
- sparser polynomials in the output
- polynomials of lower degree in the output
These are the main values that are computed in the experiments that follow. Six algorithms were used:
- the static algorithm (with a fixed input ordering, commonly used in the literature)
- the Gritzmann-Sturmfels algorithm (proposed in (Gritzmann and Sturmfels 1993), essentially a brute force search)
- the caboara-perry algorithm (proposed in (Caboara and Perry 2014), uses linear programming)
- the perturbation algorithm (new, looks for better orderings by applying perturbations to the current one)
- the random algorithm (new, does a random walk in the space of orderings)
- the local search algorithm (new, does a local search over the search space)
Due to particular traits of these algorithms, the perturbation and random algorithms only look for new orderings every 10 iterations of the Gröbner basis computation. It would also be interesting to find a better period more rigorously, but we do not do that here.
Experimental setup and environment
All algorithms were implemented in the Sage computer algebra system (version 8.8, Python version 3.7.3) and share all basic functionality from the underlying algorithm used to compute Gröbner Bases. Our implementation is based on that of (Caboara and Perry 2014). Experiments were run on an AMD FX(tm)-8150 Eight-Core Processor @ 3.60GHz machine with 32GB of RAM.
All 30 instances were extracted from Christian Eder’s benchmark library for Gröbner Bases. Each algorithm was run on every instance 30 times, the presented results corresponding to the average of these runs.
Partial results from some previous works
The following table shows the results reported in (Caboara and Perry 2014). Timings are not reported in the paper. We cannot reproduce these results, even using the code supplied in the original paper.
## Warning: Column `instance` joining factors with different levels, coercing
## to character vector## instance Original polynomials Original monomials Our polynomials
## 1 cyclicn5 11 68 10
## 2 cyclicn6 20 129 19
## 3 cyclicn7 63 1049 59
## 4 cyclicnh5 11 98 21
## 5 cyclicnh6 33 476 48
## 6 cyclicnh7 222 5181 113
## 7 katsuran6 22 54 23
## 8 katsuran7 49 104 43
## 9 katsuranh6 23 164 24
## 10 katsuranh7 46 352 52
## Our monomials
## 1 89
## 2 360
## 3 6496
## 4 296
## 5 2580
## 6 29371
## 7 593
## 8 2156
## 9 634
## 10 2600There are multiple possibilities for why we could not reproduce the results of the original paper. One is that their code may have changed between the publication of the paper and our access. As they did not provide the instances, only their names (they are all classical benchmarks in the literature) there may be slight differences in the instances themselves. An instance is a list of polynomials - they may have been provided in a different order, leading to different results. Also, one of the properties of the instances (characteristic) was not reported in the paper, so we had to choose an arbitrary value common in the literature.
For completeness, we also show the results from (Perry 2017), that uses a slightly modified version of the caboara-perry algorithm and a simple implementation in C++.
## Warning: Column `instance` joining factors with different levels, coercing
## to character vector## instance Their polynomials Their monomials Their time Our polynomials
## 1 cyclicn4 7 29 0.008 5
## 2 cyclicnh4 4 15 0.014 5
## 3 cyclicn5 13 165 0.059 10
## 4 cyclicnh5 11 148 0.025 21
## 5 cyclicn6 21 482 1.450 19
## 6 cyclicnh6 38 1340 0.386 48
## 7 cyclicn7 54 9156 243.000 59
## 8 cyclicnh7 107 27645 31.400 113
## Our monomials Our time
## 1 21 0.1133333
## 2 21 0.1711538
## 3 89 0.8042308
## 4 296 0.5724000
## 5 360 11.8400000
## 6 2580 2.9153846
## 7 6496 1634.3835714
## 8 29371 68.9342308Our implementation is much slower, but that is expected, as the implementation from (Perry 2017) is in C++ and ours is in Sage / Python. It is interesting to note, however, that for most instances their implementation is faster by almost a factor of 10. This is not the case of cyclicnh7, where it is only about 2 times faster. This points to an algorithmic advantage of the caboara-perry algorithm in this case.
Exploratory analysis
Classical reduction vs F4
Two reducers (a component of the general Gröbner Basis algorithm) were implemented: classical (based on polynomial arithmetic) and F4 (introduced in (Faugère 1999), uses matrix row reduction). F4 is usually considered to be faster in the context of traditional static Gröbner Basis algorithms. We observe this as well in our implementation, as shown by the table below (geometric means over all instances of the Static algorithm).
## # A tibble: 2 x 2
## reducer time
## <fct> <dbl>
## 1 classical 0.408
## 2 F4 0.246Is the speedup of using the F4 reducer kept for dynamic algorithms? In average, yes.
## [1] "Classical reducer running time (over all algorithms): "## [1] 1.465916## [1] "F4 reducer running time (over all algorithms):"## [1] 0.8378402The speedup of the F4 reducer is kept for most, but not all, pairs of instances and algorithms. The following graphs show results instance by instance, for three algorithms (Caboara-Perry, Static, Perturbation).
## Warning: Removed 2 rows containing missing values (geom_col).
## Warning: Removed 2 rows containing missing values (geom_col).
First, we want to visualize the running time of the algorithms per instance, comparatively, and to find the algorithm that runs the fastest for each instance.
## # A tibble: 10 x 9
## # Groups: algorithm [5]
## algorithm reducer time overhead polynomials monomials degree
## <fct> <fct> <dbl> <dbl> <dbl> <dbl> <dbl>
## 1 caboara-… classi… 2.10 1.00 21.0 481. 8.88
## 2 caboara-… F4 1.28 0.877 21.6 401. 8.74
## 3 perturba… classi… 0.617 0.252 21.9 384. 6.09
## 4 perturba… F4 0.431 0.116 25.1 479. 6.34
## 5 static classi… 0.408 NaN 28.2 529. 6.70
## 6 static F4 0.246 NaN 28.2 529. 6.70
## 7 random classi… 1.73 0.325 23.3 418. 6.56
## 8 random F4 0.483 0.0801 27.8 529. 6.89
## 9 localsea… classi… 9.68 9.16 15.8 299. 8.42
## 10 localsea… F4 8.90 8.27 18.6 282. 7.78
## # … with 2 more variables: sreductions <dbl>, timeout <int>## Warning: Removed 15 rows containing missing values (geom_point).
## Warning: Removed 15 rows containing missing values (geom_point).
Now, we compare the sizes of the output bases, in number of polynomials.
## Warning: Removed 9 rows containing missing values (geom_col).
Here, the dynamic algorithms (perturbation and caboara-perry) get better results than static for larger instances, such as cyclicn6 and cyclicnh6. All algorithms tie or are close to tying for the katsura family. It can be shown that the affine Katsura instance with parameter \(n\) has a Gröbner Basis with \(n\) polynomials. All algorithms are far from this lower bound, which means the dynamic algorithms should be improved to deal with this kind of situation better.
We should also check what happens to the degrees.
## Warning: Removed 9 rows containing missing values (geom_col).
Algorithms tie in terms of degree for most Katsuras. For the cyclics, perturbation seems to perform well, specially for the larger ones.
Quick idea: can we show that getting smaller bases rises the degree? (the graphic below looks awful, but I think it shows that the answer is yes for some instances, no to others).
## Warning: Removed 9 rows containing missing values (geom_path).
Check correlation between number of S-reductions and time.
## Warning: Removed 9 rows containing missing values (geom_point).
There is clearly a positive correlation (graphically) and computing it we get NA.
We should also test:
- polynomials and time: NA
- monomials and time: NA
- degree and time: NA
The first two are aroung \(0.5\), degree is \(0.81\). Graphing degree, we get:
## Warning: Removed 9 rows containing missing values (geom_point).
I should also measure fraction of time taken managing the queue, unrestricted vs restricted algorithms.
## Warning: Removed 9 rows containing missing values (geom_col).
#Generating some tables for the paper
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 15.93 & 2.15 & 34 & 911 & 5 & 368 \\
## cyclicn4 & 0.11 & 0.10 & 5 & 21 & 5 & 8 \\
## cyclicn5 & 0.80 & 0.48 & 10 & 89 & 15 & 87 \\
## cyclicn6 & 11.84 & 3.78 & 19 & 360 & 48 & 406 \\
## cyclicn7 & 1634.38 & 86.60 & 59 & 6496 & 203 & 2323 \\
## cyclicnh4 & 0.17 & 0.15 & 5 & 21 & 5 & 8 \\
## cyclicnh5 & 0.57 & 0.47 & 21 & 296 & 12 & 49 \\
## cyclicnh6 & 2.92 & 1.44 & 48 & 2580 & 14 & 153 \\
## cyclicnh7 & 68.93 & 28.48 & 113 & 29371 & 13 & 429 \\
## econ4 & 0.12 & 0.10 & 5 & 24 & 3 & 11 \\
## econ5 & 0.16 & 0.13 & 6 & 48 & 6 & 13 \\
## econ6 & 0.59 & 0.44 & 8 & 122 & 9 & 49 \\
## econ7 & 1.75 & 0.93 & 22 & 553 & 6 & 111 \\
## econh4 & 0.13 & 0.11 & 5 & 21 & 4 & 6 \\
## econh5 & 0.21 & 0.18 & 9 & 55 & 5 & 15 \\
## econh6 & 1.93 & 1.21 & 35 & 534 & 8 & 130 \\
## econh7 & 8.48 & 3.38 & 68 & 1985 & 15 & 324 \\
## f633 & 1.86 & 1.04 & 31 & 914 & 8 & 148 \\
## f633h & 72.66 & 10.23 & 57 & 14827 & 10 & 296 \\
## fateman & 2.37 & 1.76 & 43 & 1882 & 20 & 110 \\
## fatemanh & 0.80 & 0.63 & 22 & 925 & 12 & 47 \\
## katsuran4 & 0.14 & 0.11 & 7 & 55 & 4 & 12 \\
## katsuran5 & 0.47 & 0.39 & 12 & 193 & 6 & 32 \\
## katsuran6 & 1.21 & 0.82 & 23 & 593 & 6 & 72 \\
## katsuran7 & 4.01 & 1.29 & 43 & 2156 & 7 & 177 \\
## katsuranh4 & 0.28 & 0.25 & 8 & 58 & 4 & 15 \\
## katsuranh5 & 0.67 & 0.57 & 14 & 197 & 5 & 34 \\
## katsuranh6 & 2.58 & 2.12 & 24 & 634 & 6 & 77 \\
## katsuranh7 & 8.59 & 4.72 & 52 & 2600 & 7 & 231 \\
## noon7 & 2727.26 & 29.95 & 398 & 264267 & 19 & 3256 \\
## \hline
## \end{tabular}
## \caption{Experimental results for caboara-perry using Buchberger reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & NA & NA & NA & NA & NA & NA \\
## cyclicn4 & 0.05 & 0.03 & 7 & 30 & 6 & 29 \\
## cyclicn5 & 1.01 & 0.81 & 12 & 114 & 15 & 571 \\
## cyclicn6 & 7.58 & 2.36 & 21 & 415 & 48 & 4892 \\
## cyclicn7 & 379.04 & 103.91 & 135 & 17053 & 37 & 50945 \\
## cyclicnh4 & 0.11 & 0.09 & 7 & 29 & 8 & 38 \\
## cyclicnh5 & 0.60 & 0.49 & 20 & 309 & 12 & 314 \\
## cyclicnh6 & 8.47 & 7.49 & 43 & 2112 & 12 & 899 \\
## cyclicnh7 & 146.30 & 111.59 & 160 & 38330 & 15 & 5999 \\
## econ4 & 0.04 & 0.02 & 7 & 29 & 2 & 35 \\
## econ5 & 0.21 & 0.18 & 11 & 80 & 3 & 152 \\
## econ6 & 1.04 & 0.76 & 7 & 104 & 14 & 931 \\
## econ7 & 2.13 & 1.15 & 22 & 617 & 10 & 2359 \\
## econh4 & 0.11 & 0.09 & 10 & 44 & 6 & 56 \\
## econh5 & 0.53 & 0.46 & 20 & 153 & 10 & 288 \\
## econh6 & 1.47 & 1.33 & 29 & 381 & 7 & 384 \\
## econh7 & 7.84 & 5.33 & 79 & 2179 & 18 & 3449 \\
## f633 & 4.96 & 3.36 & 40 & 1215 & 7 & 3983 \\
## f633h & 3.88 & 2.57 & 55 & 1498 & 9 & 3370 \\
## fateman & 2.06 & 1.39 & 40 & 2056 & 17 & 680 \\
## fatemanh & 1.31 & 1.09 & 22 & 1060 & 12 & 351 \\
## katsuran4 & 0.06 & 0.04 & 7 & 49 & 4 & 44 \\
## katsuran5 & 0.33 & 0.28 & 13 & 168 & 5 & 140 \\
## katsuran6 & 1.12 & 0.94 & 21 & 518 & 6 & 375 \\
## katsuran7 & 4.68 & 1.21 & 41 & 2268 & 8 & 2677 \\
## katsuranh4 & 0.15 & 0.13 & 9 & 65 & 5 & 66 \\
## katsuranh5 & 0.45 & 0.40 & 13 & 169 & 5 & 155 \\
## katsuranh6 & 2.56 & 2.37 & 22 & 540 & 6 & 382 \\
## katsuranh7 & 6.35 & 5.38 & 48 & 2272 & 7 & 1079 \\
## noon7 & NA & NA & NA & NA & NA & NA \\
## \hline
## \end{tabular}
## \caption{Experimental results for caboara-perry using F4 reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 15.33 & 2.27 & 44 & 1300 & 4 & 393 \\
## cyclicn4 & 0.05 & 0.03 & 7 & 30 & 6 & 12 \\
## cyclicn5 & 0.48 & 0.22 & 20 & 232 & 8 & 113 \\
## cyclicn6 & 5.57 & 0.92 & 45 & 1135 & 9 & 354 \\
## cyclicn7 & 511.23 & 20.61 & 209 & 27185 & 12 & 2099 \\
## cyclicnh4 & 0.06 & 0.04 & 7 & 30 & 6 & 12 \\
## cyclicnh5 & 0.30 & 0.20 & 12 & 171 & 7 & 38 \\
## cyclicnh6 & 1.14 & 0.51 & 34 & 1540 & 9 & 102 \\
## cyclicnh7 & 44.31 & 4.17 & 121 & 28595 & 12 & 467 \\
## econ4 & 0.05 & 0.03 & 7 & 29 & 2 & 13 \\
## econ5 & 0.14 & 0.10 & 11 & 82 & 3 & 28 \\
## econ6 & 0.32 & 0.19 & 18 & 232 & 4 & 61 \\
## econ7 & 1.08 & 0.24 & 32 & 747 & 4 & 153 \\
## econh4 & 0.06 & 0.04 & 8 & 34 & 5 & 14 \\
## econh5 & 0.17 & 0.13 & 15 & 104 & 7 & 37 \\
## econh6 & 0.48 & 0.25 & 28 & 346 & 9 & 94 \\
## econh7 & NA & NA & NA & NA & NA & NA \\
## f633 & 1.18 & 0.39 & 47 & 1022 & 4 & 214 \\
## f633h & 1.28 & 0.47 & 47 & 977 & 6 & 214 \\
## fateman & 0.40 & 0.19 & 27 & 1009 & 14 & 63 \\
## fatemanh & 0.47 & 0.26 & 27 & 1009 & 14 & 63 \\
## katsuran4 & 0.07 & 0.05 & 7 & 49 & 4 & 12 \\
## katsuran5 & 0.18 & 0.12 & 13 & 168 & 5 & 31 \\
## katsuran6 & 0.52 & 0.23 & 22 & 528 & 6 & 70 \\
## katsuran7 & 2.62 & 0.63 & 41 & 1923 & 7 & 169 \\
## katsuranh4 & 0.07 & 0.06 & 7 & 49 & 4 & 12 \\
## katsuranh5 & 0.21 & 0.15 & 13 & 168 & 5 & 31 \\
## katsuranh6 & 0.57 & 0.28 & 22 & 528 & 6 & 70 \\
## katsuranh7 & 2.63 & 0.72 & 41 & 1923 & 7 & 169 \\
## noon7 & NA & NA & NA & NA & NA & NA \\
## \hline
## \end{tabular}
## \caption{Experimental results for perturbation using Buchberger reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 3.28 & 0.27 & 54 & 1796 & 4 & 2481 \\
## cyclicn4 & 0.01 & 0.00 & 7 & 30 & 6 & 43 \\
## cyclicn5 & 0.33 & 0.12 & 20 & 232 & 8 & 600 \\
## cyclicn6 & 1.61 & 0.17 & 45 & 1135 & 9 & 1710 \\
## cyclicn7 & 72.06 & 2.14 & 209 & 27185 & 12 & 13791 \\
## cyclicnh4 & 0.02 & 0.00 & 7 & 30 & 6 & 43 \\
## cyclicnh5 & 0.13 & 0.07 & 12 & 171 & 7 & 140 \\
## cyclicnh6 & 0.41 & 0.08 & 34 & 1540 & 9 & 515 \\
## cyclicnh7 & 18.35 & 0.53 & 121 & 28595 & 12 & 3705 \\
## econ4 & 0.05 & 0.04 & 7 & 29 & 2 & 35 \\
## econ5 & 0.09 & 0.05 & 11 & 82 & 3 & 162 \\
## econ6 & 0.20 & 0.10 & 18 & 232 & 4 & 417 \\
## econ7 & 0.52 & 0.08 & 32 & 747 & 4 & 1133 \\
## econh4 & 0.06 & 0.05 & 8 & 34 & 5 & 31 \\
## econh5 & 0.10 & 0.07 & 15 & 98 & 6 & 123 \\
## econh6 & 0.23 & 0.09 & 28 & 346 & 9 & 617 \\
## econh7 & 0.66 & 0.11 & 51 & 1127 & 10 & 1485 \\
## f633 & 0.88 & 0.13 & 47 & 1022 & 4 & 2278 \\
## f633h & 0.87 & 0.15 & 47 & 977 & 6 & 2025 \\
## fateman & 0.33 & 0.10 & 27 & 1009 & 14 & 471 \\
## fatemanh & 0.35 & 0.13 & 27 & 1009 & 14 & 471 \\
## katsuran4 & 0.07 & 0.05 & 7 & 49 & 4 & 44 \\
## katsuran5 & 0.13 & 0.07 & 13 & 168 & 5 & 219 \\
## katsuran6 & 0.29 & 0.08 & 22 & 528 & 6 & 537 \\
## katsuran7 & 1.34 & 0.09 & 41 & 1923 & 7 & 1346 \\
## katsuranh4 & 0.08 & 0.06 & 7 & 49 & 4 & 44 \\
## katsuranh5 & 0.14 & 0.07 & 13 & 168 & 5 & 219 \\
## katsuranh6 & 0.33 & 0.09 & 22 & 528 & 6 & 537 \\
## katsuranh7 & 1.31 & 0.12 & 41 & 1923 & 7 & 1346 \\
## noon7 & 474.42 & 1.07 & 493 & 76254 & 14 & 111944 \\
## \hline
## \end{tabular}
## \caption{Experimental results for perturbation using F4 reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 13.92 & 0.00 & 54 & 1796 & 4 & 420 \\
## cyclicn4 & 0.01 & 0.00 & 7 & 30 & 6 & 12 \\
## cyclicn5 & 0.24 & 0.00 & 20 & 232 & 8 & 113 \\
## cyclicn6 & 4.44 & 0.00 & 45 & 1135 & 9 & 354 \\
## cyclicn7 & 484.02 & 0.00 & 209 & 27185 & 12 & 2099 \\
## cyclicnh4 & 0.01 & 0.00 & 7 & 30 & 6 & 12 \\
## cyclicnh5 & 0.25 & 0.00 & 38 & 538 & 13 & 113 \\
## cyclicnh6 & 4.91 & 0.00 & 99 & 3502 & 15 & 389 \\
## cyclicnh7 & 488.70 & 0.00 & 443 & 79897 & 19 & 2199 \\
## econ4 & 0.01 & 0.00 & 7 & 29 & 2 & 13 \\
## econ5 & 0.03 & 0.00 & 11 & 82 & 3 & 28 \\
## econ6 & 0.12 & 0.00 & 18 & 232 & 4 & 61 \\
## econ7 & 0.79 & 0.00 & 32 & 747 & 4 & 153 \\
## econh4 & 0.01 & 0.00 & 8 & 34 & 5 & 14 \\
## econh5 & 0.04 & 0.00 & 15 & 104 & 7 & 37 \\
## econh6 & 0.20 & 0.00 & 28 & 346 & 9 & 94 \\
## econh7 & 1.23 & 0.00 & 51 & 1127 & 10 & 213 \\
## f633 & 0.74 & 0.00 & 47 & 1022 & 4 & 214 \\
## f633h & 0.75 & 0.00 & 47 & 977 & 6 & 214 \\
## fateman & 0.21 & 0.00 & 27 & 1009 & 14 & 63 \\
## fatemanh & 0.20 & 0.00 & 27 & 1009 & 14 & 63 \\
## katsuran4 & 0.02 & 0.00 & 7 & 49 & 4 & 12 \\
## katsuran5 & 0.05 & 0.00 & 13 & 168 & 5 & 31 \\
## katsuran6 & 0.27 & 0.00 & 22 & 528 & 6 & 70 \\
## katsuran7 & 1.91 & 0.00 & 41 & 1923 & 7 & 169 \\
## katsuranh4 & 0.02 & 0.00 & 7 & 49 & 4 & 12 \\
## katsuranh5 & 0.05 & 0.00 & 13 & 168 & 5 & 31 \\
## katsuranh6 & 0.27 & 0.00 & 22 & 528 & 6 & 70 \\
## katsuranh7 & 1.82 & 0.00 & 41 & 1923 & 7 & 169 \\
## noon7 & 224.42 & 0.00 & 495 & 71153 & 13 & 2892 \\
## \hline
## \end{tabular}
## \caption{Experimental results for static using Buchberger reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 2.33 & 0.00 & 54 & 1796 & 4 & 2136 \\
## cyclicn4 & 0.01 & 0.00 & 7 & 30 & 6 & 29 \\
## cyclicn5 & 0.17 & 0.00 & 20 & 232 & 8 & 364 \\
## cyclicn6 & 0.91 & 0.00 & 45 & 1135 & 9 & 1272 \\
## cyclicn7 & 51.60 & 0.00 & 209 & 27185 & 12 & 11117 \\
## cyclicnh4 & 0.01 & 0.00 & 7 & 30 & 6 & 29 \\
## cyclicnh5 & 0.11 & 0.00 & 38 & 538 & 13 & 350 \\
## cyclicnh6 & 1.01 & 0.00 & 99 & 3502 & 15 & 1344 \\
## cyclicnh7 & 36.74 & 0.00 & 443 & 79897 & 19 & 8752 \\
## econ4 & 0.01 & 0.00 & 7 & 29 & 2 & 35 \\
## econ5 & 0.03 & 0.00 & 11 & 82 & 3 & 149 \\
## econ6 & 0.09 & 0.00 & 18 & 232 & 4 & 417 \\
## econ7 & 0.48 & 0.00 & 32 & 747 & 4 & 1133 \\
## econh4 & 0.01 & 0.00 & 8 & 34 & 5 & 31 \\
## econh5 & 0.03 & 0.00 & 15 & 104 & 7 & 142 \\
## econh6 & 0.11 & 0.00 & 28 & 346 & 9 & 468 \\
## econh7 & 0.43 & 0.00 & 51 & 1127 & 10 & 1185 \\
## f633 & 0.84 & 0.00 & 47 & 1022 & 4 & 2098 \\
## f633h & 0.56 & 0.00 & 47 & 977 & 6 & 1776 \\
## fateman & 0.21 & 0.00 & 27 & 1009 & 14 & 433 \\
## fatemanh & 0.25 & 0.00 & 27 & 1009 & 14 & 433 \\
## katsuran4 & 0.02 & 0.00 & 7 & 49 & 4 & 44 \\
## katsuran5 & 0.04 & 0.00 & 13 & 168 & 5 & 140 \\
## katsuran6 & 0.16 & 0.00 & 22 & 528 & 6 & 389 \\
## katsuran7 & 1.00 & 0.00 & 41 & 1923 & 7 & 1077 \\
## katsuranh4 & 0.03 & 0.00 & 7 & 49 & 4 & 44 \\
## katsuranh5 & 0.04 & 0.00 & 13 & 168 & 5 & 140 \\
## katsuranh6 & 0.24 & 0.00 & 22 & 528 & 6 & 389 \\
## katsuranh7 & 1.01 & 0.00 & 41 & 1923 & 7 & 1077 \\
## noon7 & 290.10 & 0.00 & 495 & 71153 & 13 & 80906 \\
## \hline
## \end{tabular}
## \caption{Experimental results for static using F4 reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 86.94 & 3.06 & 49 & 1577 & 4 & 510 \\
## cyclicn4 & 0.13 & 0.08 & 7 & 30 & 6 & 12 \\
## cyclicn5 & 0.54 & 0.22 & 20 & 238 & 8 & 120 \\
## cyclicn6 & 7.20 & 0.77 & 44 & 1119 & 11 & 399 \\
## cyclicn7 & 491.97 & 11.23 & 209 & 27185 & 12 & 2099 \\
## cyclicnh4 & 0.09 & 0.05 & 7 & 30 & 6 & 12 \\
## cyclicnh5 & 0.45 & 0.20 & 31 & 438 & 11 & 99 \\
## cyclicnh6 & 27.68 & 1.65 & 46 & 2065 & 13 & 470 \\
## cyclicnh7 & 790.06 & 17.42 & 181 & 45324 & 17 & 1476 \\
## econ4 & 0.05 & 0.04 & 7 & 29 & 2 & 13 \\
## econ5 & 0.12 & 0.09 & 11 & 82 & 3 & 28 \\
## econ6 & 0.27 & 0.14 & 18 & 232 & 4 & 61 \\
## econ7 & 0.95 & 0.15 & 32 & 747 & 4 & 153 \\
## econh4 & 0.06 & 0.04 & 8 & 34 & 5 & 14 \\
## econh5 & 88.86 & 3.53 & 17 & 123 & 8 & 489 \\
## econh6 & 1.76 & 0.28 & 31 & 407 & 9 & 167 \\
## econh7 & NA & NA & NA & NA & NA & NA \\
## f633 & 5.57 & 0.48 & 41 & 1075 & 5 & 234 \\
## f633h & 39.07 & 1.15 & 46 & 1047 & 6 & 346 \\
## fateman & 9.30 & 0.71 & 25 & 1017 & 13 & 181 \\
## fatemanh & 115.28 & 4.57 & 23 & 1049 & 13 & 491 \\
## katsuran4 & 0.06 & 0.04 & 7 & 49 & 4 & 12 \\
## katsuran5 & 0.17 & 0.09 & 13 & 168 & 5 & 34 \\
## katsuran6 & 0.41 & 0.14 & 22 & 528 & 6 & 70 \\
## katsuran7 & 2.26 & 0.36 & 41 & 1923 & 7 & 169 \\
## katsuranh4 & 0.06 & 0.04 & 7 & 49 & 4 & 12 \\
## katsuranh5 & 0.15 & 0.09 & 13 & 168 & 5 & 31 \\
## katsuranh6 & 0.44 & 0.16 & 22 & 528 & 6 & 70 \\
## katsuranh7 & 2.34 & 0.35 & 41 & 1923 & 7 & 169 \\
## noon7 & NA & NA & NA & NA & NA & NA \\
## \hline
## \end{tabular}
## \caption{Experimental results for random using Buchberger reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 2.80 & 0.13 & 54 & 1796 & 4 & 2481 \\
## cyclicn4 & 0.01 & 0.00 & 7 & 30 & 6 & 43 \\
## cyclicn5 & 0.31 & 0.10 & 20 & 237 & 8 & 604 \\
## cyclicn6 & 1.53 & 0.14 & 45 & 1135 & 9 & 1710 \\
## cyclicn7 & 66.48 & 1.13 & 209 & 27185 & 12 & 13791 \\
## cyclicnh4 & 0.02 & 0.00 & 7 & 30 & 6 & 43 \\
## cyclicnh5 & 0.31 & 0.10 & 38 & 533 & 14 & 682 \\
## cyclicnh6 & 1.81 & 0.12 & 65 & 2594 & 14 & 2032 \\
## cyclicnh7 & 59.97 & 0.34 & 443 & 79897 & 19 & 14430 \\
## econ4 & 0.06 & 0.04 & 7 & 29 & 2 & 36 \\
## econ5 & 0.09 & 0.05 & 8 & 65 & 5 & 150 \\
## econ6 & 0.14 & 0.05 & 17 & 229 & 4 & 414 \\
## econ7 & 0.49 & 0.05 & 32 & 747 & 4 & 1133 \\
## econh4 & 0.06 & 0.05 & 7 & 33 & 5 & 36 \\
## econh5 & 0.10 & 0.04 & 16 & 117 & 7 & 245 \\
## econh6 & 0.23 & 0.05 & 29 & 404 & 8 & 647 \\
## econh7 & 11.55 & 0.10 & 56 & 1516 & 9 & 8562 \\
## f633 & 0.76 & 0.06 & 45 & 998 & 4 & 2360 \\
## f633h & 0.67 & 0.06 & 47 & 990 & 6 & 2076 \\
## fateman & 0.35 & 0.11 & 26 & 1004 & 14 & 514 \\
## fatemanh & 0.32 & 0.10 & 27 & 1009 & 14 & 471 \\
## katsuran4 & 0.06 & 0.04 & 6 & 47 & 4 & 86 \\
## katsuran5 & 0.11 & 0.05 & 13 & 168 & 5 & 219 \\
## katsuran6 & 0.27 & 0.05 & 22 & 528 & 6 & 537 \\
## katsuran7 & 1.26 & 0.05 & 41 & 1923 & 7 & 1346 \\
## katsuranh4 & 0.07 & 0.05 & 7 & 49 & 4 & 44 \\
## katsuranh5 & 0.12 & 0.05 & 13 & 168 & 5 & 219 \\
## katsuranh6 & 0.27 & 0.05 & 22 & 528 & 6 & 537 \\
## katsuranh7 & 1.10 & 0.06 & 41 & 1923 & 7 & 1346 \\
## noon7 & 352.98 & 0.45 & 495 & 71153 & 13 & 116239 \\
## \hline
## \end{tabular}
## \caption{Experimental results for random using F4 reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & NA & NA & NA & NA & NA & NA \\
## cyclicn4 & 0.42 & 0.32 & 5 & 21 & 5 & 8 \\
## cyclicn5 & 7.34 & 6.83 & 10 & 89 & 15 & 105 \\
## cyclicn6 & 133.30 & 120.09 & 17 & 351 & 48 & 346 \\
## cyclicn7 & NA & NA & NA & NA & NA & NA \\
## cyclicnh4 & 0.34 & 0.30 & 5 & 21 & 5 & 8 \\
## cyclicnh5 & 4.55 & 4.42 & 21 & 293 & 12 & 49 \\
## cyclicnh6 & 41.15 & 39.59 & 48 & 1706 & 13 & 150 \\
## cyclicnh7 & NA & NA & NA & NA & NA & NA \\
## econ4 & 0.37 & 0.35 & 5 & 22 & 3 & 11 \\
## econ5 & 0.98 & 0.93 & 6 & 48 & 6 & 15 \\
## econ6 & 4.33 & 4.17 & 9 & 139 & 7 & 44 \\
## econ7 & 28.14 & 27.06 & 18 & 482 & 12 & 109 \\
## econh4 & 1.01 & 0.97 & 8 & 83 & 6 & 15 \\
## econh5 & 6.14 & 6.01 & 14 & 358 & 7 & 35 \\
## econh6 & 62.41 & 61.49 & 31 & 1799 & 8 & 110 \\
## econh7 & 683.08 & 676.53 & 66 & 5589 & 10 & 306 \\
## f633 & 19.57 & 18.44 & 42 & 1031 & 7 & 192 \\
## f633h & 3132.36 & 3123.84 & 34 & 4677 & 8 & 141 \\
## fateman & 30.59 & 29.89 & 44 & 1933 & 20 & 113 \\
## fatemanh & 37.95 & 37.55 & 33 & 1321 & 16 & 81 \\
## katsuran4 & 0.59 & 0.55 & 7 & 49 & 4 & 12 \\
## katsuran5 & 2.88 & 2.75 & 12 & 182 & 6 & 32 \\
## katsuran6 & 37.26 & 36.12 & 8 & 257 & 20 & 93 \\
## katsuran7 & 48.00 & 45.06 & 44 & 2200 & 7 & 181 \\
## katsuranh4 & 0.84 & 0.78 & 7 & 55 & 4 & 12 \\
## katsuranh5 & 3.11 & 2.98 & 14 & 194 & 5 & 34 \\
## katsuranh6 & 25.50 & 24.72 & 30 & 828 & 8 & 109 \\
## katsuranh7 & NA & NA & NA & NA & NA & NA \\
## noon7 & NA & NA & NA & NA & NA & NA \\
## \hline
## \end{tabular}
## \caption{Experimental results for localsearch using Buchberger reducer}
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## butcher8 & 837.40 & 823.00 & 31 & 1019 & 5 & 7019 \\
## cyclicn4 & 0.41 & 0.38 & 6 & 28 & 8 & 69 \\
## cyclicn5 & 11.19 & 9.63 & 11 & 102 & 15 & 3524 \\
## cyclicn6 & 188.25 & 174.14 & 53 & 1347 & 13 & 9172 \\
## cyclicn7 & NA & NA & NA & NA & NA & NA \\
## cyclicnh4 & 0.56 & 0.53 & 7 & 27 & 8 & 64 \\
## cyclicnh5 & 4.36 & 4.12 & 17 & 254 & 10 & 876 \\
## cyclicnh6 & 90.99 & 86.12 & 59 & 2113 & 13 & 5903 \\
## cyclicnh7 & NA & NA & NA & NA & NA & NA \\
## econ4 & 0.28 & 0.25 & 7 & 29 & 2 & 74 \\
## econ5 & 1.16 & 0.99 & 8 & 55 & 5 & 302 \\
## econ6 & 8.00 & 7.07 & 8 & 136 & 9 & 1840 \\
## econ7 & 39.67 & 37.61 & 23 & 647 & 8 & 4002 \\
## econh4 & 0.65 & 0.60 & 8 & 33 & 6 & 121 \\
## econh5 & 2.79 & 2.62 & 20 & 156 & 10 & 656 \\
## econh6 & 12.01 & 10.96 & 36 & 527 & 9 & 2786 \\
## econh7 & 40.26 & 38.68 & 47 & 1113 & 8 & 2864 \\
## f633 & 13.51 & 12.08 & 32 & 679 & 7 & 3694 \\
## f633h & 63.01 & 61.52 & 44 & 977 & 6 & 3996 \\
## fateman & 29.34 & 27.36 & 42 & 1834 & 20 & 2761 \\
## fatemanh & 30.16 & 29.37 & 29 & 1127 & 15 & 1479 \\
## katsuran4 & 0.63 & 0.58 & 7 & 54 & 4 & 128 \\
## katsuran5 & 2.16 & 2.03 & 13 & 170 & 5 & 413 \\
## katsuran6 & 19.28 & 17.96 & 20 & 583 & 8 & 2218 \\
## katsuran7 & 142.63 & 132.00 & 34 & 1938 & 10 & 8726 \\
## katsuranh4 & 0.78 & 0.75 & 7 & 55 & 4 & 92 \\
## katsuranh5 & 13.36 & 12.50 & 30 & 459 & 12 & 2237 \\
## katsuranh6 & 11.34 & 10.56 & 23 & 586 & 6 & 1244 \\
## katsuranh7 & NA & NA & NA & NA & NA & NA \\
## noon7 & NA & NA & NA & NA & NA & NA \\
## \hline
## \end{tabular}
## \caption{Experimental results for localsearch using F4 reducer}
## \end{table}Checking out Random results
Every instance / reducer has been run at least 2 times.
## # A tibble: 60 x 3
## # Groups: reducer [2]
## reducer instance n
## <fct> <fct> <int>
## 1 classical butcher8 8
## 2 classical cyclicn4 6
## 3 classical cyclicn5 11
## 4 classical cyclicn6 12
## 5 classical cyclicn7 7
## 6 classical cyclicnh4 13
## 7 classical cyclicnh5 17
## 8 classical cyclicnh6 7
## 9 classical cyclicnh7 13
## 10 classical econ4 5
## # … with 50 more rows#Checking out GS and GFans
## # A tibble: 7 x 3
## instance minG mindeg
## <fct> <int> <int>
## 1 econ5 5 3
## 2 econh4 4 3
## 3 katsuranh4 7 4
## 4 katsuran4 4 4
## 5 cyclicn4 5 5
## 6 cyclicnh4 4 4
## 7 econ4 4 2## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrrrr}
## \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred & minG & mindeg \\
## \hline
## econ5 & 115.21 & 114.90 & 10 & 70 & 3 & 33 & 5 & 3 \\
## econh4 & 461.15 & 459.52 & 10 & 51 & 6 & 158 & 4 & 3 \\
## katsuranh4 & 5.67 & 5.60 & 7 & 49 & 4 & 30 & 7 & 4 \\
## katsuran4 & 0.85 & 0.74 & 7 & 52 & 4 & 11 & 4 & 4 \\
## cyclicn4 & 0.90 & 0.87 & 5 & 21 & 5 & 11 & 5 & 5 \\
## cyclicnh4 & 1.88 & 1.85 & 4 & 17 & 4 & 10 & 4 & 4 \\
## econ4 & 1.10 & 1.05 & 4 & 18 & 2 & 12 & 4 & 2 \\
## \hline
## \end{tabular}
## \caption{Experimental results for GS using Buchberger reducer}
## \end{table}Behavior in cyclics / homogeneous cyclics
## Warning: Removed 1 rows containing missing values (geom_path).
## Warning: Removed 1 rows containing missing values (geom_path).
## Warning: Removed 1 rows containing missing values (geom_path).
## Warning: Removed 1 rows containing missing values (geom_path).
## Warning: Removed 1 rows containing missing values (geom_path).
## Warning: Removed 1 rows containing missing values (geom_path).
Generating data on Gröbner fans
## Warning: Removed 1 rows containing missing values (geom_point).
## Warning: Removed 1 rows containing missing values (geom_point).
## Warning: Removed 1 rows containing missing values (geom_point).
## Warning: Removed 2 rows containing missing values (geom_point).
## Warning: Removed 1 rows containing missing values (geom_point).
## Warning: Removed 3 rows containing missing values (geom_point).
I noticed perturbation and random are measuring overhead 0 when the reducer is F4. Why? Is it a problem in the measurement or in the R code?
## Adding missing grouping variables: `instance`, `algorithm`## # A tibble: 60 x 3
## # Groups: instance, algorithm [60]
## instance algorithm dynamic
## <fct> <fct> <dbl>
## 1 butcher8 perturbation 0.270
## 2 butcher8 random 0.134
## 3 cyclicn4 perturbation 0
## 4 cyclicn4 random 0
## 5 cyclicn5 perturbation 0.121
## 6 cyclicn5 random 0.0992
## 7 cyclicn6 perturbation 0.169
## 8 cyclicn6 random 0.139
## 9 cyclicn7 perturbation 2.14
## 10 cyclicn7 random 1.13
## # … with 50 more rowsThe problem is that in a few cases, the overhead is 0. Then, the geometric mean is 0. I can just drop zeroes from the gmean computation.
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:59 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lllrrrrrr}
## \hline
## instance & Algorithm & Reducer & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\
## \hline
## cyclicnh6 & caboara-perry & classical & 2.92 & 1.44 & 48.00 & 2580.00 & 14.00 & 153.00 \\
## cyclicnh6 & caboara-perry & F4 & 8.47 & 7.49 & 43.00 & 2112.00 & 12.00 & 899.00 \\
## cyclicnh6 & perturbation & classical & 1.14 & 0.51 & 34.00 & 1540.00 & 9.00 & 102.00 \\
## cyclicnh6 & perturbation & F4 & 0.41 & 0.08 & 34.00 & 1540.00 & 9.00 & 515.00 \\
## cyclicnh6 & static & classical & 4.91 & 0.00 & 99.00 & 3502.00 & 15.00 & 389.00 \\
## cyclicnh6 & static & F4 & 1.01 & 0.00 & 99.00 & 3502.00 & 15.00 & 1344.00 \\
## cyclicnh6 & random & classical & 27.68 & 1.65 & 46.83 & 2065.00 & 13.67 & 470.17 \\
## cyclicnh6 & random & F4 & 1.81 & 0.12 & 65.33 & 2594.00 & 14.00 & 2032.33 \\
## cyclicnh6 & localsearch & classical & 41.15 & 39.59 & 48.00 & 1706.00 & 13.00 & 150.00 \\
## cyclicnh6 & localsearch & F4 & 90.99 & 86.12 & 59.00 & 2113.00 & 13.00 & 5903.00 \\
## cyclicnh7 & caboara-perry & classical & 68.93 & 28.48 & 113.00 & 29371.00 & 13.00 & 429.00 \\
## cyclicnh7 & caboara-perry & F4 & 146.30 & 111.59 & 160.00 & 38330.00 & 15.00 & 5999.00 \\
## cyclicnh7 & perturbation & classical & 44.31 & 4.17 & 121.00 & 28595.00 & 12.00 & 467.00 \\
## cyclicnh7 & perturbation & F4 & 18.35 & 0.53 & 121.00 & 28595.00 & 12.00 & 3705.00 \\
## cyclicnh7 & static & classical & 488.70 & 0.00 & 443.00 & 79897.00 & 19.00 & 2199.00 \\
## cyclicnh7 & static & F4 & 36.74 & 0.00 & 443.00 & 79897.00 & 19.00 & 8752.00 \\
## cyclicnh7 & random & classical & 790.06 & 17.42 & 181.17 & 45324.33 & 17.33 & 1476.00 \\
## cyclicnh7 & random & F4 & 59.97 & 0.34 & 443.00 & 79897.00 & 19.00 & 14430.00 \\
## cyclicnh7 & localsearch & classical & NA & NA & NA & NA & NA & NA \\
## cyclicnh7 & localsearch & F4 & NA & NA & NA & NA & NA & NA \\
## cyclicnh8 & static & F4 & 1950.10 & 0.00 & 1182.00 & 676462.00 & 29.00 & 72296.00 \\
## cyclicnh8 & perturbation & classical & 1777.19 & 68.64 & 455.00 & 415782.00 & 17.00 & 2220.00 \\
## cyclicnh8 & perturbation & F4 & 1820.61 & 2.51 & 455.00 & 415782.00 & 17.00 & 50872.00 \\
## cyclicnh8 & static & classical & 11114.02 & 0.00 & 1182.00 & 676462.00 & 29.00 & 7026.00 \\
## cyclicnh8 & caboara-perry & classical & 16730.38 & 14118.22 & 538.00 & 486535.00 & 20.00 & 2710.00 \\
## cyclicnh8 & random & classical & 6732.86 & 93.15 & 635.19 & 547311.89 & 21.59 & 3674.48 \\
## cyclicnh8 & random & F4 & 6233.03 & 2.43 & 804.07 & 616809.19 & 22.96 & 109107.44 \\
## \hline
## \end{tabular}
## \caption{Results for some homogeneous Cyclic ideals.}
## \end{table}Caboara, Massimo, and John Perry. 2014. “Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm.” Applicable Algebra in Engineering, Communications and Computing 25 (1-2): 99–117. https://doi.org/10.1007/s00200-014-0216-5.
Faugère, Jean-Charles. 1999. “A new efficient algorithm for computing Gröbner bases (F4).” Journal of Pure and Applied Algebra 139 (1). Elsevier: 61–88.
Gritzmann, Peter, and Bernd Sturmfels. 1993. “Minkowski Addition of Polytopes: Computational Complexity and Application to Gröbner Bases.” SIAM J. Disc. Math. 6 (2): 246–69.
Perry, John. 2017. “Exploring the Dynamic Buchberger Algorithm.” In Proceedings of the 2017 International Symposium on Symbolic and Algebraic Computation, 365–72.